package _220318;

import java.io.*;
import java.util.*;

/**
 * @author yoonalim
 * @create 2022-03-18-9:20
 */
public class _青蛙跳杯子 {
    static String src, dest;
    //使用map来记录，防止循环重复
    static Map<String, Boolean> vis = new HashMap<String, Boolean>();

    /**
     * https://blog.csdn.net/a1439775520/article/details/97620201
     * @param args
     * @throws IOException
     */

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        src = br.readLine();
        dest = br.readLine();
        br.close();
        System.out.println(bfs(src, dest));
    }

    private static int bfs(String src, String dest) {
        //典型的BFS用LinkedList实现Queue
        Queue<Node> q = new LinkedList<>();
        Node node = new Node(src, 0);
        q.add(node);
        vis.put(node.str, true);

        while (q.size() != 0) {
            node = q.poll();
            // 如果当前字符串和结果字符串dest相等，直接输出
            if (check(node.str)) {
                return node.step;
            }

            char[] str = node.str.toCharArray();
            int step = node.step;

            for (int i = 0; i < str.length; i++) {
                if (str[i] == '*') {    // 如果当前位是空杯子 则跳过，我们判断的是青蛙，而不是空杯子
                    continue;
                }
                for (int j = -3; j <= 3; j++) { // 隔着j个格子跳(j < 0 : 向左跳 j > 0 : 向右跳)
                    // 越界 或 想要跳到的位置不是空杯子 或没有跳跃（j == 0） 放弃这次的j步跳跃
                    if (i + j < 0 || i + j >= str.length || j == 0 || str[i + j] != '*') {
                        continue;
                    }
                    // 否则 进行跳跃 交换位置
                    str = swap(str, i, j);
                    // 新建节点
                    node = new Node(String.valueOf(str), step + 1);
                    // 观察以前有没有相同的字符串，如果有只能是循环了，continue
                    if (!vis.containsKey(node.str)) {
                        q.add(node);
                        vis.put(node.str, true);
                    }
                    str = swap(str, i, j);  // 回溯 使用完交换回来
                }
            }
        }
        // 全部循环完，还没有结果
        return -1;
    }

    /**
     * 间隔距离step 交换位置（i, i + step）
     * @param str
     * @param i
     * @param step
     * @return
     */
    private static char[] swap(char[] str, int i, int step) {
        char t = str[i];
        str[i] = str[step + i];
        str[step + i] = t;
        return str;
    }

    /**
     * 判断是否与结果字符串dest相同
     * @param str
     * @return
     */
    private static boolean check(String str) {
        if (dest.equalsIgnoreCase(String.valueOf(str))) {   // 必须使用valueOf()
            return true;
        } else {
            return false;
        }
    }
}

class Node {
    int step = 0;
    String str;

    public Node(String str, int step) {
        this.step = step;
        this.str = str;
    }
}
